package history.hot100.difficult;

import history.hot100.TreeNode;

public class LeetCode_124 {
    private int ret;
    public int maxPathSum(TreeNode root) {
        ret = Integer.MIN_VALUE;
        dfs(root);
        return ret;
    }

    private int dfs (TreeNode treeNode) {
        if (treeNode == null) return 0;
        int leftSubTreeSum = Math.max(0, dfs(treeNode.left));
        int rightSubTreeRight = Math.max(0, dfs(treeNode.right));

        ret = Math.max(ret, treeNode.val+leftSubTreeSum+rightSubTreeRight);
        return treeNode.val+Math.max(leftSubTreeSum, rightSubTreeRight);
    }
}
